//
//  ArraySolution.swift
//  Swift-Learning-Demo
//
//  Created by yuan xiaodong on 2020/12/22.
//  Copyright © 2020 yuan. All rights reserved.
//

import Foundation

class ArraySolution {
    init() {
        
    }
    
    // MARK: - *********** 【1】两数之和 难度:简单 ***********
    /*
     给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
     你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
     示例:
     给定 nums = [2, 7, 11, 15], target = 9
     因为 nums[0] + nums[1] = 2 + 7 = 9
     所以返回 [0, 1]
     */
    //时间复杂度是 O(n)
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var table:[Int:Int] = [Int:Int]()
        for (firstIndex, num) in nums.enumerated() {
            let res: Int = target - num
            //可选链接
            if let secondIndex = table[res]
            {
                return [secondIndex,firstIndex]
            }
            else
            {
                table[num] = firstIndex
            }
        }
        return [-1,-1]
    }
    
    // MARK: - *********** 【26】删除排序数组中的重复项 难度:简单 ***********
    /*
     给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
     不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

     示例 1:
     给定数组 nums = [1,1,2],
     函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
     你不需要考虑数组中超出新长度后面的元素。
     
     示例 2:
     给定 nums = [0,0,1,1,1,2,2,3,3,4],
     函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
     你不需要考虑数组中超出新长度后面的元素。
     */
    func removeDuplicates(_ nums: inout [Int]) -> Int {
        var length : Int = 0
        if nums.count > 0{
            length = 1
            var prev : Int = nums[0]
            var currentIndex = 1
            var index : Int = 1
            while index < nums.count {
                while(index < nums.count && nums[index] == prev){
                    index += 1
                }
                if index < nums.count && nums[index] != prev {
                    nums[currentIndex] = nums[index]
                    prev = nums[currentIndex]
                    length += 1
                    currentIndex += 1
                }
            }
        }
        return length
    }
    
    // MARK: - *********** 【27】移除元素 难度:简单 ***********
    /*
     给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
     不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
     元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

     示例 1:
     给定 nums = [3,2,2,3], val = 3,
     函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
     你不需要考虑数组中超出新长度后面的元素。
     
     示例 2:
     给定 nums = [0,1,2,2,3,0,4,2], val = 2,
     函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
     注意这五个元素可为任意顺序。

     你不需要考虑数组中超出新长度后面的元素。
     */
    func removeElement(_ nums: inout [Int], _ val: Int) -> Int {
        var i = 0, j = nums.count - 1
        while i <= j {
            if nums[i] == val {
               //根据数组索引互换两个元素
                nums.swapAt(i, j)
                j -= 1
            } else {
                i += 1
            }
        }
        return j + 1
    }
    
    // MARK: - *********** 【35】搜索插入位置 难度:简单 ***********
    /*
     给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     你可以假设数组中无重复元素。

     示例 1:
     输入: [1,3,5,6], 5
     输出: 2
     
     示例 2:
     输入: [1,3,5,6], 2
     输出: 1
     
     示例 3:
     输入: [1,3,5,6], 7
     输出: 4
     
     示例 4:
     输入: [1,3,5,6], 0
     输出: 0
     */
    func searchInsert(_ nums: [Int], _ target: Int) -> Int {
        //如果nums为nil则返回0
        if nums.isEmpty{return 0}
        //二分查找也称折半查找（Binary Search）
        var low:Int = 0
        var high:Int = nums.count-1
        while(low <= high)
        {
            let mid = (low+high)/2
            if nums[mid]==target
            {
                return mid
            }
            else if nums[mid]<target
            {
                low = mid+1
            }
            else
            {
                high = mid-1
            }
        }
        return low
    }
    
    // MARK: - *********** 【面试题 10.01】合并排序的数组 难度:简单 ***********
    /*
     给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。
     初始化 A 和 B 的元素数量分别为 m 和 n。
     
     示例:
     输入:
     A = [1,2,3,0,0,0], m = 3
     B = [2,5,6],       n = 3

     输出: [1,2,2,3,5,6]
     
     说明:
     A.length == n + m
     */
    func merge(_ A: inout [Int], _ m: Int, _ B: [Int], _ n: Int) {
        var i = 0
        var j = 0
        var arr = [Int]()
        
        while i < m && j < n {
            if A[i] < B[j] {
                arr.append(A[i])
                i+=1
            } else {
                arr.append(B[j])
                j+=1
            }
        }

        while i < m {
            arr.append(A[i])
            i+=1
        }

        while j < n {
            arr.append(B[j])
            j+=1
        }

        A = arr
    }
    
    // MARK: - *********** 【121】买卖股票的最佳时机 难度:简单 ***********
    /*
     给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
     如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
     注意：你不能在买入股票前卖出股票。

     示例 1:
     输入: [7,1,5,3,6,4]
     输出: 5
     解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
          注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
    
     示例 2:
     输入: [7,6,4,3,1]
     输出: 0
     解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
     */
    func maxProfit(_ prices: [Int]) -> Int {
        if prices == nil || prices.count == 0
        {
            return 0
        }
        let counts = prices.count
        var arr:Array = Array(repeating: 0, count: counts)
        var minPrice = prices[0]
        for i in 1..<counts
        {
            minPrice = (minPrice < prices[i]) ? minPrice : prices[i]
            arr[i] = (arr[i - 1] > (prices[i] - minPrice)) ? arr[i - 1] : (prices[i] - minPrice)
        }
        return arr[counts-1]
    }
    
    // MARK: - *********** 【121】买卖股票的最佳时机 难度:简单 ***********
    /*
     给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
     进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

     示例 1：
     输入：nums1 = [1,3], nums2 = [2]
     输出：2.00000
     解释：合并数组 = [1,2,3] ，中位数 2
     
     示例 2：
     输入：nums1 = [1,2], nums2 = [3,4]
     输出：2.50000
     解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
     
     示例 3：
     输入：nums1 = [0,0], nums2 = [0,0]
     输出：0.00000
     
     示例 4：
     输入：nums1 = [], nums2 = [1]
     输出：1.00000
     
     示例 5：
     输入：nums1 = [2], nums2 = []
     输出：2.00000
      
     提示：
     nums1.length == m
     nums2.length == n
     0 <= m <= 1000
     0 <= n <= 1000
     1 <= m + n <= 2000
     -106 <= nums1[i], nums2[i] <= 106
     */
    func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
        var i = 0, j = 0
        var m = nums1.count, n = nums2.count
        var arr1 = nums1, arr2 = nums2
        if m > n {
            swap(&m, &n)
            swap(&arr1, &arr2)
        }
        let half = (m + n) / 2

        var leftMax = 0, rightMin = 0

        // 长度为m的数组分割，有m+1种分割方法，所以 0 <= i <= m
        var min = 0, max = m
        while min <= max {
            i = (min + max) / 2
            j = half - i
            if i > 0 && arr1[i-1] > arr2[j] {
                max = i - 1
            } else if i < m && arr2[j-1] > arr1[i] {
                min = i + 1
            } else {
                // arr1 所有元素都在左边，则min(Right) = arr2[j]
                if i == m {
                    rightMin = arr2[j]
                } else if j == n {
                    rightMin = arr1[i]
                } else {
                    rightMin = arr1[i] > arr2[j] ? arr2[j] : arr1[i]
                }

                if (m + n) % 2 == 1 {
                    return Double(rightMin)
                }

                if i == 0 {
                    leftMax = arr2[j - 1]
                } else if j == 0 {
                    leftMax = arr1[i - 1]
                } else {
                    leftMax = arr1[i-1] > arr2[j-1] ? arr1[i-1] : arr2[j-1]
                }
                return Double(leftMax + rightMin) / 2.0
            }
        }
        return 0
    }
    
    // MARK: - *********** 【11】盛最多水的容器 难度:中等 ***********
    /**
     给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

     说明：你不能倾斜容器。
     输入：[1,8,6,2,5,4,8,3,7]
     输出：49
     解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
     
     示例 2：
     输入：height = [1,1]
     输出：1
     
     示例 3：
     输入：height = [4,3,2,1,4]
     输出：16
     
     示例 4：
     输入：height = [1,2,1]
     输出：2
      
     提示：

     n = height.length
     2 <= n <= 3 * 104
     0 <= height[i] <= 3 * 104
     
     */
    func maxArea(_ height: [Int]) -> Int {
        var max = 0
        var start = 0
        var end = height.count - 1
        
        while start < end {
            let width = end - start
            var high = 0
            let startH = height[start]
            let endH = height[end]
            if  startH < endH {
                high = height[start]
                start = start + 1
            }else{
                high = height[end]
                end = end - 1
            }
            let temp = width * high
            if temp > max {
                max = temp
            }
        }
        return max
    }
    
    // MARK: - *********** 买卖股票的最佳时机 II ***********
    /**
     给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。

     在每一天，你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它，然后在 同一天 出售。
     返回 你能获得的 最大 利润 。

      

     示例 1:

     输入: prices = [7,1,5,3,6,4]
     输出: 7
     解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
          随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
     示例 2:

     输入: prices = [1,2,3,4,5]
     输出: 4
     解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
          注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
     示例 3:

     输入: prices = [7,6,4,3,1]
     输出: 0
     解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
     */
}
